package org.chnxi.study.datastructrues.sort;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 基数排序算法
 */
public class RadixSorting {

    public static void main(String[] args) {
        int arr[] = {53,3,542,748,14,214};
        System.out.println("原数组："+Arrays.toString(arr));
        System.out.println("分步骤讲解：");
        radixSortByStep(arr);

        System.out.println("直接排序：");
        int arr2[] = {53,3,542,748,14,214};
        radixSort(arr2);
        System.out.println("排序结果："+ Arrays.toString(arr2));

        System.out.println("测试大量数据的执行耗时：");
        int numCount = 8000000;
        int[] randomArr = new int[numCount];
        for (int i =0; i<numCount; i++){
            randomArr[i] = (int) (Math.random()*numCount);
        }

        long start = System.currentTimeMillis();
        int[] randomArrTmp = new int[numCount];
        radixSort(randomArr);
        long end = System.currentTimeMillis();
        System.out.println("执行耗时："+(end - start));

    }

    /**
     * 分步骤拆解
     * @param arr
     */
    public static void radixSortByStep(int[] arr){
        // 定义一个二维数组表示10个桶
        // 一维长度是10标识0~9
        // 二维长度采用最大arr.length
        int[][] bucket = new int[10][arr.length];
        //记录每个桶的存入元素数量
        int[] bucketElementCounts = new int[10];

        //第一轮，针对每个元素的个位进行排序
        for(int j = 0; j < arr.length; j++){
            //取出每个元素的个位
            int digitOfElement = arr[j] % 10;
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;
        }

        //按照桶中的元素顺序放入到原来的数组
        int index = 0;
        for (int k = 0; k < 10; k++){
            //如果桶中有数据，才放入到原数组
            if(bucketElementCounts[k] != 0){
                for (int l = 0; l < bucketElementCounts[k]; l++){
                    //取出元素，放入到arr中
                    arr[index] = bucket[k][l];
                    index++;
                }
            }
            //需要将桶中的数量重新计0
            bucketElementCounts[k] = 0;
        }

        System.out.println("第一轮，对个位的排序："+ Arrays.toString(arr));

        //第二轮，针对每个元素的十位进行排序
        for(int j = 0; j < arr.length; j++){
            //取出每个元素的个位
            int digitOfElement = arr[j] / 10 % 10;
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;
        }

        //按照桶中的元素顺序放入到原来的数组
        index = 0;
        for (int k = 0; k < 10; k++){
            //如果桶中有数据，才放入到原数组
            if(bucketElementCounts[k] != 0){
                for (int l = 0; l < bucketElementCounts[k]; l++){
                    //取出元素，放入到arr中
                    arr[index] = bucket[k][l];
                    index++;
                }
            }
            //需要将桶中的数量重新计0
            bucketElementCounts[k] = 0;
        }

        System.out.println("第二轮，对个位的排序："+ Arrays.toString(arr));

        //第三轮，针对每个元素的白位进行排序
        for(int j = 0; j < arr.length; j++){
            //取出每个元素的个位
            int digitOfElement = arr[j] / 100 % 10;
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;
        }

        //按照桶中的元素顺序放入到原来的数组
        index = 0;
        for (int k = 0; k < 10; k++){
            //如果桶中有数据，才放入到原数组
            if(bucketElementCounts[k] != 0){
                for (int l = 0; l < bucketElementCounts[k]; l++){
                    //取出元素，放入到arr中
                    arr[index] = bucket[k][l];
                    index++;
                }
            }
            //需要将桶中的数量重新计0
            bucketElementCounts[k] = 0;
        }

        System.out.println("第三轮，对个位的排序："+ Arrays.toString(arr));

    }


    /**
     * 完整排序过程
     * @param arr
     */
    public static void radixSort(int[] arr){
        //需要先找到数组中最大的数
        int max = arr[0];
        for (int i = 0; i < arr.length; i++){
            if(arr[i] > max){
                max = arr[i];
            }
        }
        //得到最大的数是几位
        int maxLength = (max + "").length();

        // 定义一个二维数组表示10个桶
        int[][] bucket = new int[10][arr.length];
        //记录每个桶的存入元素数量
        int[] bucketElementCounts = new int[10];

        for (int i = 0, n =1; i < maxLength; i++,n*=10){
            for(int j = 0; j < arr.length; j++){
                //取出每个元素的个位
                int digitOfElement = arr[j] / n % 10;
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }

            //按照桶中的元素顺序放入到原来的数组
            int index = 0;
            for (int k = 0; k < 10; k++){
                //如果桶中有数据，才放入到原数组
                if(bucketElementCounts[k] != 0){
                    for (int l = 0; l < bucketElementCounts[k]; l++){
                        //取出元素，放入到arr中
                        arr[index] = bucket[k][l];
                        index++;
                    }
                }
                //需要将桶中的数量重新计0
                bucketElementCounts[k] = 0;
            }
        }
    }
}
